package leetcode.editor.cn;

/**
 * Copyright (C) 2023 思创数码科技股份有限公司
 * <p/>
 * 版权所有
 * <p/>
 * 类名　　  : P221
 * 功能概要  :
 *
 * @Author : yangwk
 * @Date : 2024/1/14 10:46
 */
public class P221 {
    public static void main(String[] args) {


        System.out.println(new P221().maximalSquareDP(new char[][]{
                {'1','1','1','0','0'},
                {'1','1','1','0','0'},
                {'1','1','1','1','1'},
                {'0','1','1','1','1'},
                {'0','1','1','1','1'},
                {'0','1','1','1','1'}}
        ));
    }
    //动态规划
    // 在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
    public int maximalSquareDP(char[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        int maxLen = 0;
        int[][] dp = new int[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == '1') {
                    if (i == 0 && j == 0) {
                        dp[i][j] = 1;
                        maxLen = 1;
                    } else if (i > 0 && j > 0) {
                        dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1])+1;
                    } else if (i > 0) {
                        dp[i][j] = Math.min(dp[i - 1][j], dp[i][j]) + 1;
                    } else if (j > 0) {
                        dp[i][j] = Math.min(dp[i ][j-1], dp[i][j]) + 1;
                    }
                    if (dp[i][j] > maxLen) {
                        maxLen = dp[i][j];
                    }
                }
            }
        }
        return maxLen * maxLen;
    }

    // 在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
    public int maximalSquare(char[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        int maxLen = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == '1') {
                    if (maxLen == 0) {
                        maxLen = 1;
                    }
                    int maxRow = Math.min(row - i, col - j);
                    if (maxRow <= maxLen) {
                        continue;
                    }
                    int start = 1;
                    while (start < maxRow) {
                        boolean find = true;
                        for (int l = i; l <=i + start; l++) {
                            if (matrix[l][j + start] == '0') {
                                find = false;
                                break;
                            }
                        }
                        for (int k = j; k <=j + start && find; k++) {
                            if (matrix[i + start][k] == '0') {
                                find = false;
                                break;
                            }
                        }
                        if (find) {
                            maxLen = Math.max(start+1, maxLen);
                        } else {
                            break;
                        }
                        start++;
                    }
                }
            }
        }
        return maxLen * maxLen;
    }


}
